package com.shm.leetcode;

import java.util.*;

/**
 * 399. 除法求值
 * 给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
 *
 * 另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
 *
 * 返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。
 *
 *
 *
 * 注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
 *
 *
 *
 * 示例 1：
 *
 * 输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
 * 输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
 * 解释：
 * 条件：a / b = 2.0, b / c = 3.0
 * 问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
 * 结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
 * 示例 2：
 *
 * 输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
 * 输出：[3.75000,0.40000,5.00000,0.20000]
 * 示例 3：
 *
 * 输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
 * 输出：[0.50000,2.00000,-1.00000,-1.00000]
 *
 *
 * 提示：
 *
 * 1 <= equations.length <= 20
 * equations[i].length == 2
 * 1 <= Ai.length, Bi.length <= 5
 * values.length == equations.length
 * 0.0 < values[i] <= 20.0
 * 1 <= queries.length <= 20
 * queries[i].length == 2
 * 1 <= Cj.length, Dj.length <= 5
 * Ai, Bi, Cj, Dj 由小写英文字母与数字组成
 * @author SHM
 */
public class CalcEquation {
    /**
     * 方法一：广度优先搜索
     * 我们可以将整个问题建模成一张图：给定图中的一些点（变量），以及某些边的权值（两个变量的比值），试对任意两点（两个变量）求出其路径长（两个变量的比值）。
     *
     * 因此，我们首先需要遍历 \textit{equations}equations 数组，找出其中所有不同的字符串，并通过哈希表将每个不同的字符串映射成整数。
     *
     * 在构建完图之后，对于任何一个查询，就可以从起点出发，通过广度优先搜索的方式，不断更新起点与当前点之间的路径长度，直到搜索到终点为止。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(ML+Q\cdot(L+M))O(ML+Q⋅(L+M))，其中 MM 为边的数量，QQ 为询问的数量，LL 为字符串的平均长度。构建图时，需要处理 MM 条边，每条边都涉及到 O(L)O(L) 的字符串比较；处理查询时，每次查询首先要进行一次 O(L)O(L) 的比较，然后至多遍历 O(M)O(M) 条边。
     *
     * 空间复杂度：O(NL+M)O(NL+M)，其中 NN 为点的数量，MM 为边的数量，LL 为字符串的平均长度。为了将每个字符串映射到整数，需要开辟空间为 O(NL)O(NL) 的哈希表；随后，需要花费 O(M)O(M) 的空间存储每条边的权重；处理查询时，还需要 O(N)O(N) 的空间维护访问队列。最终，总的复杂度为 O(NL+M+N) = O(NL+M)O(NL+M+N)=
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/evaluate-division/solution/chu-fa-qiu-zhi-by-leetcode-solution-8nxb/
     * @param equations
     * @param values
     * @param queries
     * @return
     */
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int n = equations.size();
        int vars = 0;
        Map<String,Integer> var = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (!var.containsKey(equations.get(i).get(0))){
                var.put(equations.get(i).get(0),vars++);
            }
            if (!var.containsKey(equations.get(i).get(1))){
                var.put(equations.get(i).get(1),vars++);
            }
        }

        // 对于每个点，存储其直接连接到的所有点及对应的权值
        List<Pair>[] edges = new List[vars];
        for (int i = 0; i < vars; i++) {
            edges[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            int va = var.get(equations.get(i).get(0)),vb = var.get(equations.get(i).get(1));
            edges[va].add(new Pair(vb,values[i]));
            edges[vb].add(new Pair(va,1.0/values[i]));
        }

        int size = queries.size();
        double[] rets = new double[size];
        for (int i = 0; i < size; i++) {
            List<String> query = queries.get(i);
            double ret = -1.0;
            if (var.containsKey(query.get(0))&&var.containsKey(query.get(1))){
                int va =var.get(query.get(0)),vb = var.get(query.get(1));
                if (va==vb){
                    ret = 1.0;
                }else{
                    Queue<Integer> points = new LinkedList<>();
                    points.offer(va);
                    double[] rations = new double[vars];
                    Arrays.fill(rations,-1.0);
                    rations[va] = 1.0;

                    while (!points.isEmpty()&&rations[vb]<0){
                        Integer x = points.poll();
                        for (Pair pair : edges[x]) {
                            int y = pair.index;
                            double val = pair.value;
                            if (rations[y]<0){
                                rations[y] = rations[x]*val;
                                points.offer(y);
                            }
                        }
                    }
                    ret = rations[vb];
                }
            }
            rets[i] = ret;
        }
        return rets;
    }

    class Pair{
        int index;
        double value;

        Pair(int index,double value){
            this.index = index;
            this.value = value;
        }
    }
}
